#include "DoubleLinkList.h"

Status DoubleLinkList::InitList(void)
{
    L = (DoubleLinkNode*)malloc(sizeof(DoubleLinkNode));
    if (L)
        L->next = L->prev = L;
    else
        exit(OVERFLOW);

    return OK;
}

Status DoubleLinkList::DestoryList(void)
{
    // p指向第一个节点
    DoubleLinkNode *q, *p = L->next;

    while (p != L) {
        q = p->next;
        free(p);
        p = q;
    }

    free(L);
    L = nullptr;

    return OK;
}

Status DoubleLinkList::ClearList(void)
{
    // p指向第一个节点
    DoubleLinkNode *q, *p = L->next;

    while (p != L) {
        q = p->next;
        free(p);
        p = q;
    }

    L->next = L->prev = L;

    return OK;
}

Status DoubleLinkList::ListEmpty(void)
{
    if (L->next == L && L->prev == L)
        return TRUE;
    else
        return FALSE;
}

int DoubleLinkList::ListLength(void)
{
    // p指向第一个节点
    DoubleLinkNode *p = L->next;
    int i = 0;

    while (p != L) {
        i++;
        p = p->next;
    }

    return i;
}

Status DoubleLinkList::GetElem(int i, ElemType *e)
{
    // p指向第一个节点
    DoubleLinkNode *p = L->next;
    int j = 0;

    while (p != L && j < i) {
        p = p->next;
        j++;
    }

    if (p == L || j > i)
        return FALSE;

    *e = p->e;

    return OK;
}

int DoubleLinkList::LocateElem(ElemType e, Status(*compare)(ElemType, ElemType))
{
    // p指向第一个节点
    DoubleLinkNode *p = L->next;
    int i = 0;

    while (p != L) {
        i++;
        if (compare(p->e, e))
            return i;

        p = p->next;
    }
    return 0;
}

Status DoubleLinkList::PriorElem(ElemType cur, ElemType *prev)
{
    // p指向第2个节点
    DoubleLinkNode *p = L->next->next;

    while (p != L) {
        if (p->e == cur) {
            *prev = p->prev->e;
            return TRUE;
        }
        p = p->next;
    }

    return FALSE;
}

Status DoubleLinkList::NextElem(ElemType cur, ElemType *next)
{
    // p指向第2个节点
    DoubleLinkNode *p = L->next->next;

    while (p != L) {
        if (p->prev->e == cur) {
            *next = p->e;
            return TRUE;
        }
        p = p->next;
    }

    return FALSE;
}

/**
 * 在第i个元素之前插入
 */
Status DoubleLinkList::ListInsert(int i, ElemType e)
{
    DoubleLinkNode *p, *s;

    if (i < 0 || i > ListLength())
        return ERROR;

    p = GetElemP(i-1);
    if (!p)
        return ERROR;

    s = (DoubleLinkNode*)malloc(sizeof(DoubleLinkNode));
    s->e = e;

    /* 在第i-1元素的后面插入 */
    s->prev = p;
    s->next = p->next;

    p->next->prev = s;
    // 这个放到最后，防止链表断裂
    p->next = s;

    return OK;
}

/**
 * 删除第i个元素
 */
Status DoubleLinkList::ListDelete(int i, ElemType *e)
{
    DoubleLinkNode *p;

    if (i <0)
        return ERROR;

    p = GetElemP(i);
    if (!p)
        return ERROR;

    *e = p->e;

    p->prev->next = p->next;
    p->next->prev = p->prev;

    free(p);

    return OK;
}

Status DoubleLinkList::ListTraverse(void)
{
    // p指向头节点
    DoubleLinkNode *p = L->next;
    while (p != L) {
        print(&p->e);
        p = p->next;
    }

    return OK;
}

Status DoubleLinkList::ListHeadInsert(ElemType e)
{
    return OK;
}

Status DoubleLinkList::ListTailInsert(ElemType e)
{
    return OK;
}